package com.lei.sort;

import com.lei.linearsearch.ArrayGenerator;

import java.util.Arrays;

/**
 * @Author LeiXiaoLei
 * @Date 2022/9/2 12:02
 * @Version 1.0
 */
public class LSDSort {

    private LSDSort() {
    }

    public static void sort(String[] arr, int W) {

        for (String s : arr)
            if (s.length() != W)
                throw new IllegalArgumentException("All Strings' length must be the same.");

        int R = 256;
        int[] cnt = new int[R];
        int[] index = new int[R + 1];
        String[] temp = new String[arr.length];
        for (int r = W - 1; r >= 0; r--) {

            // O(n)
            Arrays.fill(cnt, 0);
            for (String s : arr)
                cnt[s.charAt(r)]++;

            // O(R)
            for (int i = 0; i < R; i++)
                index[i + 1] = index[i] + cnt[i];

            // O(n)
            for (String s : arr) {
                temp[index[s.charAt(r)]] = s;
                index[s.charAt(r)]++;
            }

            // O(n)
            for (int i = 0; i < arr.length; i++)
                arr[i] = temp[i];
        }
    }

    public static void main(String[] args) {


        // int n = 100000, w = 200;
        int n = 1000000, w = 2;
        String[] arr = ArrayGenerator.generateRandomStringArray(n, w);
        String[] arr2 = Arrays.copyOf(arr, arr.length);

        SortingHelper2.sortTest("QuickSort", arr);
        SortingHelper2.sortTest("LSDSort", arr2);
    }
}
